

class Solution:

    def findMedianSortedArrays(self, num1, num2):
        
        l1 = num1
        l2 = num2

        m = len(num1)
        n = len(num2)
        flag_1 = False
        flag_2 = False

        res = []

        if (m + n) % 2 == 0:
            flag_2 = True
        else:
            flag_1 = True


        for i in range(m + n):

            if not l1:
                res += l2
                break

            if not l2:
                res += l1
                break
            
            if l1[0] <= l2[0]:
                res.append(l1.pop(0))
            else:
                res.append(l2.pop(0))

            # 提前结束，减少搜索的次数
            if flag_2 and i == (m+n)//2:
                return (res[-1] + res[-2]) / 2
            if flag_1 and i == (m+n) // 2 :
                return res[-1]

        
        if len(res) % 2 == 0:
            # print(res)
            # print(res[(m+n) // 2], res[(m+n) // 2 - 1])
            return (res[(m+n) // 2] + res[(m+n) // 2 - 1]) / 2
        
        return res[(m+n) // 2]



if __name__ == "__main__":

    num1 = [1, 3]
    num2 = [2, 4, 6, 8]

    sol = Solution()
    res = sol.findMedianSortedArrays(num1, num2)
    print(res)

            





